#include <iostream>
#include <fstream>
#include <vector>
#include <regex>
#include <iomanip>

#define BUFFER_SIZE 128
#define MAX_COUNT 128
using namespace std;

/**
 * 从文件中读取并且解析文件内容
 * @param path 文件路径
 * @param arr 二维数组
 * @return 数组行个数
 */
int ParseFileText(const char *path , int arr[MAX_COUNT][MAX_COUNT])
{
    ifstream ifs(path);
    if (!ifs.is_open())
    {
        cout << "打开文件失败" << endl;
        return 0;
    }
    int n;
    ifs >> n;
    for (int j = 0; j < n; ++j)
        for (int i = 0; i < n; ++i)
            arr[j][i] = 0;
    char str[BUFFER_SIZE];
    ifs.getline(str, BUFFER_SIZE);
    int i = 0;
    while (!ifs.eof())
    {
        ifs.getline(str, BUFFER_SIZE);
        [str, &arr, &i]()
        {
            string s = str;
            regex p("([0-9]+)\\D{0,}");
            int j = 0;
            for (sregex_iterator it(s.begin(), s.end(), p), end;
                    it != end; ++it)
                arr[i][j++] = atoi(it->str().c_str());
            ++i;
        }();
    }
    ifs.close();
    return n;
}

/**
 * 获得能经过的最大路径
 * @param arr 传入的二维数组
 * @param re 结果（经过的位置）
 * @param n 行个数
 * @return 最大权重
 */
int MaxWeight(int arr[MAX_COUNT][MAX_COUNT] , int n)
{
    int wg = 0;
    int tmp[n][n];
    for (int l = 0; l < n; ++l)
        for (int i = 0; i < n; ++i)
            tmp[l][i] = 0;
    tmp[0][0] = arr[0][0];
    for (int i = 1; i < n; ++i)
        for (int j = 0; j <= i; ++j)
            tmp[i][j] = arr[i][j] + (tmp[i-1][j] > tmp[i-1][j-1] ? tmp[i-1][j] : tmp[i-1][j-1]);
    for (int k = 0; k < n; ++k)
        wg = wg > tmp[n-1][k] ? wg : tmp[n-1][k];
    return wg;
}

/**
 * 向文件写入一个数字
 * @param path 文件路径
 * @param number 要写入的数字
 * @return 成功1失败0
 */
int WriteFile(const char* path , int number)
{
    ofstream ofs(path);

    if(!ofs.is_open())
    {
        cout << "打开文件错误" << endl;
        return 0;
    }

    ofs << number;

    ofs.close();

    return 1;
}

int main()
{
    int arr[MAX_COUNT][MAX_COUNT];
    auto count = ParseFileText("input.txt" , arr);

    auto wg = MaxWeight(arr , count);

    cout << "最大经过权重为 : " << wg << endl;

    WriteFile("Output.txt" , wg);

    return 0;
}